package com.ztom.top100;

import java.util.Arrays;

/**
 * 戳气球
 * <p>
 * https://leetcode-cn.com/problems/burst-balloons/
 *
 * @author ZhangTao
 */
public class Code79MaxCoins {

    public int maxCoins1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        // 补足两边的 1
        int[] help = new int[n + 2];
        help[0] = 1;
        help[help.length - 1] = 1;
        System.arraycopy(nums, 0, help, 1, n);
        int[][] dp = new int[n + 2][n + 2];
        for (int[] d : dp) {
            Arrays.fill(d, -1);
        }

        return process(help, 0, n + 1, dp);
    }

    /**
     * 戳爆(l, r)的气球
     *
     * @param help
     * @param l
     * @param r
     * @return
     */
    private int process(int[] help, int l, int r, int[][] dp) {
        if (dp[l][r] != -1) {
            return dp[l][r];
        }

        if (l >= r - 1) {
            // (l, r) 之间没有气球了
            return 0;
        }

        // (l, r)
        for (int i = l + 1; i < r; i++) {
            int sum = help[l] * help[i] * help[r];
            sum += process(help, l, i, dp) + process(help, i, r, dp);
            dp[l][r] = Math.max(dp[l][r], sum);
        }
        return dp[l][r];
    }


    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        // 补足两边的 1
        int[] help = new int[n + 2];
        help[0] = 1;
        help[help.length - 1] = 1;
        System.arraycopy(nums, 0, help, 1, n);

        int[][] dp = new int[n + 2][n + 2];
        // 真实数组
        for (int l = n - 1; l >= 0; l--) {
            for (int r = l + 2; r <= n + 1; r++) {
                for (int k = l + 1; k < r; k++) {
                    int sum = help[l] * help[k] * help[r];
                    sum += dp[l][k] + dp[k][r];
                    dp[l][r] = Math.max(dp[l][r], sum);
                }
            }
        }
        return dp[0][n + 1];
    }
}
